/*
 * File:   disjoint_sets.c
 * Author: aishwarya
 *
 * Created on March 20, 2011, 12:50 PM
 * Implementation of Disjoint Sets data structure.
 * Uses Union by Rank & Path Compression heuristics
 */

#include "../DataStructures/avdtech.h"
#include "disjoint_sets.h"

void set_make(disjoint_sets *s, int v) {
    s->P[v] = v; /* Make each node its own parent */
    s->R[v] = 1; /* Rank (num of elements) in this set is 1 */
}

void set_init(disjoint_sets *s, int nelements) {
    int i;
    s->nelements = nelements;
    /* Allocating n+1 elements, as graph vertices/nodes/set elements start from 1 */
    s->P = (Parent *) calloc(s->nelements+1, sizeof(Parent)) ;
    s->R = (int *) calloc(s->nelements+1, sizeof(int)) ;
    for (i = 1; i <= s->nelements; i++)
        set_make(s, i);
}

Parent set_find(disjoint_sets *s, int v) {
    if (v != s->P[v])
        s->P[v] = set_find(s, s->P[v]);

    return s->P[v];
}

int set_is_same_component(disjoint_sets *s, int u, int v) {
    return (set_find(s, u) == set_find(s, v)) ;
}

/* This function is passed Representative elements of sets which are to
 * be merged */
void set_union_p(disjoint_sets *s, Parent pu, Parent pv) {
    if (pu == pv)
        return ;
    
    if (s->R[pu] > s->R[pv])
        s->P[pv] = pu;
    else {
        s->P[pu] = pv;
        if (s->R[pu] == s->R[pv])
            s->R[pv]++;
    }
}

/* This function is passed two elements whose set have to be merged */
void set_union_c(disjoint_sets *s, int u, int v) {
    Parent pu, pv ;
    
    pu = set_find(s, u) ;
    pv = set_find(s, v) ;

    set_union_p(s, pu, pv) ;
}

void set_clean(disjoint_sets *s) {
    free(s->P) ;
    free(s->R) ;
}

